package com.example.interview.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月28日 下午5:04:36
 * 两路归并排序算法思路
	分而治之(divide - conquer);每个递归过程涉及三个步骤
	第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
	第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
	第三, 合并: 合并两个排好序的子序列,生成排序结果.
	
	归并排序：每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。线性对数阶
	冒泡排序：最好的时间复杂度为O(n)，最坏时间复杂度为：O(n2)，冒泡排序总的平均时间复杂度为：O(n2) 平方阶
	归并优于冒泡
	https://www.cnblogs.com/chengxiao/p/6194356.html
 */
public class Test00guibingpaixu {

	public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

	private static void sort(int[] arr) {
		// 在排序前先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
		int[] temp=new int[arr.length];
		sort(arr,0,arr.length-1,temp);
		
	}

	private static void sort(int[] arr, int left, int right, int[] temp) {
		if (left<right) {
			int mid=(left+right)/2;
			sort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
			sort(arr, mid+1, right, temp);//右边归并排序，使得右子序列有序
			
			merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
		}
	}

	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		int i=left;//左序列指针
		int j=mid+1;//右序列指针
		int t=0;//临时数组指针
		
		while(i<=mid&&j<=right) {
			if (arr[i]<=arr[j]) {
				temp[t++]=arr[i++];
			}else {
				temp[t++]=arr[j++];
			}
		}
		while(i<=mid) {
			//将左边剩余元素填充到temp中
			temp[t++]=arr[i++];
		}
		while(j<=right) {
			//将右序列剩余元素填充到temp中
			temp[t++]=arr[j++];
		}
		t=0;
		//将temp中的元素拷贝到原数组
		while(left<=right) {
			arr[left++]=temp[t++];
		}
	}
	
	
}
